/*
 * BitVector.cpp
 *
 *  Created on: 28/08/2014
 *      Author: santosma
 */

#include "BitVector.h"

//vetor com palavras de apenas um bit em cada posição
BASE word[] = {1 << 0, 1 << 1, 1 << 2, 1 << 3, 1 << 4, 1 << 5, 1 << 6, 1 << 7, 1 << 8,
		1 << 9, 1 << 10, 1 << 11, 1 << 12, 1 << 13, 1 << 14, 1 << 15, 1 << 16,
		1 << 17, 1 << 18, 1 << 19, 1 << 20, 1 << 21, 1 << 22, 1 << 23, 1 << 24,
		1 << 25, 1 << 26, 1 << 27, 1 << 28, 1 << 29, 1 << 30, 1 << 31
};

BitVector::BitVector(long n){
	size = (n >> LOGBASE) + 1;
	this->n = n;
	elems = new BASE[size];
}

BitVector::~BitVector(){
	delete elems;
}

void BitVector::setAll(){
	for(int i = 0; i < size ; i++) elems[i] = ~0;
	for(int i = n; i < size*BASESIZE; i++) unset(i);
}

void BitVector::unsetAll(){
	for(int i = 0; i < size ; i++) elems[i] = 0;
}

void BitVector::set(long i){
	int id = i >> LOGBASE;
	int index = i & DIVREST;
	elems[id] = elems[id] | word[index];
}

void BitVector::unset(long i){
	int id = i >> LOGBASE;
	int index= i & DIVREST;
	elems[id] = elems[id] & ~(word[index]);
}

bool BitVector::isSet(long i){
	int id = i >> LOGBASE;
	int index= i & DIVREST;
	return (elems[id] & word[index]) != 0;
}

long BitVector::count(){
	long cont = 0;
	for(int i = 0; i < size; i++) cont += __builtin_popcount(elems[i]);
	return cont;
}

void BitVector::dot(BitVector* v){
	for(int i = 0; i < size; i++) elems[i] = elems[i]&v->elems[i];
}

void BitVector::sum(BitVector* v){
	for(int i = 0; i < size; i++) elems[i] = elems[i]|v->elems[i];
}

void BitVector::diff(BitVector* v){
	for(int i = 0; i < size; i++) elems[i] = elems[i]& (~v->elems[i]);
}

int BitVector::firstOne(){
	int ff = 0;
	for(int i = 0; i < size; i++){
		if(elems[i] == 0) ff += BASESIZE;
		else return ff + __builtin_ffs(elems[i]) - 1;
	}
	return ff-1;
}

int BitVector::firstOneAfter(int i){
	if(i >= n || i < 0) return n;
	int index = i & DIVREST;
	int ff = BASESIZE*(i >> LOGBASE);
	for(int j = index; j < BASESIZE; j++){
		if(isSet(j)) return j + ff;
	}
	ff += BASESIZE;
	for(int j = (i >> LOGBASE) + 1; j < size; j++){
		if(elems[j] == 0) ff += BASESIZE;
		else return ff + __builtin_ffs(elems[j]) - 1;
	}
	return ff-1;
}

BitVector* BitVector::copy(){
	BitVector* u = new BitVector(n);
	for(int i = 0; i < size; i++) u->elems[i] = elems[i];
	return u;
}


void BitVector::print(){
	printf("VETOR \n");
	for(int i = 0; i < n; i++){
		if(isSet(i)) printf(" 1 ");
		else printf(" 0 ");
	}
	printf("\n");
}
